package com.zp.self.module.level_4_算法练习.数据结构.二叉树;
import org.junit.Test;

import java.util.LinkedList;

/**
 * @author By ZengPeng
 */
public class 力扣_1022_从根到叶的二进制数之和 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_1022_从根到叶的二进制数之和().new Solution();
        System.out.println(solution.sumRootToLeaf(init()));
    }

    /**
     题目：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
         例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
         对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
         返回这些数字之和。题目数据保证答案是一个 32 位 整数。

         示例 1：
         输入：root = [1,0,1,0,1,0,1]
         输出：22
         解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

         示例 2：
         输入：root = [0]
         输出：0

     分析：【P 💖💖】
        1.dfs: 栈记录
                --执行耗时:1 ms,击败了23.39% 的Java用户
                --编码耗时:[18:07]
        --优化：传递前面节点合成的数据，节省内存、加快计算
                --执行耗时:0 ms,击败了100.00% 的Java用户

     边界值 & 注意点：
        1.
     **/
public static TreeNode init(){
    TreeNode treeNode2 = new TreeNode(0, new TreeNode(0),new TreeNode(1));
    TreeNode treeNode3 = new TreeNode(1,new TreeNode(0),new TreeNode(1));
    return new TreeNode(1,treeNode2,treeNode3);
}
//leetcode submit region begin(Prohibit modification and deletion)
public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root,0);
    }

    private int dfs(TreeNode root, int pro) {
        int sum = 0;
        pro = (pro<<1)|root.val;
        if(root.left==null && root.right==null)
            return pro;
        if(root.left!=null)
            sum+=dfs(root.left, pro);
        if(root.right!=null)
            sum+=dfs(root.right, pro);
        return sum;
    }

   /* private int total(LinkedList<Integer> list) {
        int res = 0;
        for (Integer numb : list)
            res = (res<<1) | numb;
        return res;
    }*/
}
//leetcode submit region end(Prohibit modification and deletion)

}